#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <string.h>
#include <math.h>

typedef int HPDataType;

typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}Heap;

void swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}


//堆的向下调整法:
void AdjustDown(int *a, int n, int parent)
{
    int child = parent * 2 + 1;

    while(child < n)
    {
        if(child + 1 < n && a[child+1] < a[child])
        {
            child++;
        }
        else if(a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

//堆的向上调整法:
void AdjustUp(int* a, int child)
{
    int parent = (child-1) / 2;
    while(child > 0)
    {
        if(a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child-1) / 2;
        }
        else
        {
            break;
        }
    }
}

void HeapInit(Heap* php, HPDataType* a, int n)
{
    assert(php);

    HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if(tmp == nullptr)
    {
        printf("malloc fail");
        exit(-1);
    }

    php->a = tmp;
    memcpy(php->a, a, sizeof(HPDataType)*n);
    php->size = n;
    php->capacity = n;
    int i = 0;

    //建堆:php->size-1是最后一位的下标, 再-1是左子树;
    for(int i = (php->size - 1-1) / 2; i >= 0; i--)
    {
        AdjustDown(php->a, n, i);
    }
}

void HeapDestory(Heap* php)
{
    assert(php);

    free(php->a);
    php->a = nullptr;
    php->size = php->capacity = 0;
}

int depth(int n)
{
    assert(n >= 0);

    if(n > 0)
    {
        int m = 2;
        int height = 1;
        while(m < n + 1)
        {
            m *= 2;
            height++;
        }
        return height;
    }
    else
    {
        return 0;
    }
}


void HeapPrint(Heap* php)
{
    assert(php);

    for(int i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");


    int h = depth(php->size);
    int N = (int)pow(2, h) -1;
    int space = N-1;
    int row = 1;
    int pos = 0;

    while(1)
    {
        for(int i = 0; i < space; i++)
        {
            printf(" ");
        }

        int count = (int)pow(2, row - 1);
        while(count--)
        {
            printf("%02d ", php->a[pos++]);
            if(pos == php->size)
            {
                printf("\n");
                return;
            }
            int distance = (space + 1) * 2;
            while(distance--)
            {
                printf(" ");
            }
        }
        printf("\n");
        row++;
        space = (space + 1) / 2;
    }
}


void HeapPush(Heap* php, HPDataType x)
{
    assert(php);

    if(php->size == php->capacity)
    {
        HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * php->capacity * 2);
        if(tmp == nullptr)
        {
            printf("malloc fail");
            exit(-1);
        }

        php->a = tmp;
        php->capacity *= 2;
    }

    php->a[php->size] = x;
    php->size += 1;

    AdjustUp(php->a, php->size-1);
}

bool HeapEmpty(Heap* php)
{
    assert(php);

    return php->a == 0;
}

void HeapPop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));

    swap(&php->a[0], &php->a[php->size]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));

    return php->a[0];
}

int HeapSize(Heap* php)
{
    assert(php);
    return php->size;
}